package demo8;

/**
 * 01背包-最后一块石头的重量II
 */
public class test5 {
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int m = sum / 2;
        int[][] dp = new int[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= stones[i-1]) {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j - stones[i-1]] + stones[i-1]);
                }
            }
        }
        return sum - 2*dp[n][m];
    }

    // 优化
    public int lastStoneWeightII2(int[] stones) {
        int n = stones.length;
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int m = sum / 2;
        int[] dp = new int[m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= stones[i-1]; j--) {
                dp[j] = Math.max(dp[j],dp[j - stones[i-1]] + stones[i-1]);
            }
        }
        return sum - 2*dp[m];
    }
}
